Leetcode 挑戰 Day 01 [前言與 1. Two Sum]

13th鐵人賽

meow_kai

2021-09-04 03:55:26

2420 瀏覽

分享至

前言

我是一位程式設計的初學者，對程式設計非常有興趣，希望在這個系列的Leetcode挑戰中能提升自我，以及把我所知的知識以精簡的方式分享給大家，當中如有參考資料皆會附在文末，也很歡迎大家給我建議和指導！

1. Two Sum

TwoSum是Leetcode題庫中的第一題，也是許多人第一次來到這個網站會先著手的一題，雖然按照題目編號刷題並不是一個很好的作法，但這一題確實是一個很好的題目，需要用到資料結構的技巧，並且展示了演算法的重要性，因此挑選這一題作為第一天的挑戰。

題目

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

題目的意思是希望我們能在nums這個整數列表中，找到兩兩相加能夠剛好等於target的元素所在位置(index)，並用陣列的方式回傳，並且題目保證洽好只會有一組符合。

暴力解法

看到這個題目最先想到的就是用兩個迴圈直接把題目的要求，把每個可能的組合相加後確認有無符合target的答案，有的話就回傳相對的位置，以下是C++的程式碼

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target){
        for(int i=0;i<nums.size();i++){
            for(int j=i+1;j<nums.size();j++){
                if(nums[i] + nums[j] == target){
                    return {i, j};
                }
            }
        }
        return {};
    }
};

這樣的解法在Leetcode上以C++是會通過的，但是非常的慢，主要的原因就在於這樣子兩層迴圈的暴力解法，所使用的時間複雜度是big O(n^2)，以下說明更為巧妙的解法。

HashMap解法

HahsMap是由Key和value所組成，在HashMap中Key是唯一的，且一個Key會對應到一個Value，而透過HashMap可以實現以接近big O(1)的時間複雜度來確認資料是否存在，以及其對應的值Value為何。
因此在本題中我們可以先建立一個HashMap，並透過一個for迴圈，以元素為Key、其所在位置（index）為Value存進HashMap，並且每次以Target減去走訪的整數，如果此結果正好為HashMap中某個Key，那我們就針對相對應的value和當下走訪到的位置，存成一個陣列並回傳，這樣一來可以將時間複雜度降低到big O(n)。以下是程式碼的實現

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target){
        unordered_map<int, int> Hash_Map; //建立HashMap
        for(int i=0;i<nums.size();i++){
            if (Hash_Map.find(target-nums[i]) != Hash_Map.end()){ // 如果找到在HashMap中存在想要找的Key
                return {i, Hash_Map[target-nums[i]]}; //那就回傳現在的index與相對應的Value
            }
            Hash_Map[nums[i]] = i; //存入HashMap
        }
        return {};
    }
};